1. Field of the Invention
The present invention relates to computer systems and methods in which a hash table can be accessed by software running concurrently on one or more processors. More particularly, the invention concerns an improved system and method that allows lock-free lookups of hash table elements while efficiently permitting concurrent update operations in which list element keys are updated.
2. Description of the Prior Art
By way of background, hash tables provide fast access times to items indexed by a key. They typically consist of an array of hash buckets each containing a linked list of elements that hash to the same bucket. As with most shared data structures, reading and writing a hash table concurrently by multiple tasks (e.g., processes, threads, etc.) requires some form of synchronization, and this synchronization incurs some overhead. The use of reader-writer locks, and the use of fine-grained per-bucket locking, can greatly reduce this overhead. However, any form of locking causes a serious performance hit even in the absence of contention due to the use of expensive atomic instructions, and due to bypassing the cache to read from memory.
It would be desirable to provide a hash table implementation that requires no locking or expensive instructions on the read side. Readers could thus run concurrently with writers and the contents of a hash bucket could be changed while readers traverse it. A challenge that has impeded the removal of read-side locking for hash table operations is how to perform a key update on a hash table element that results in the element being moved from one bucket to another. By way of example, this situation arises in the context of in-memory file system tree images used by operating systems to perform file name lookups for locating files maintained on block storage devices. In a directory entry hash table, directory entries (representing files) are assigned to hash buckets according to a hash algorithm based on their name and name of their parent directory. When a file's name is changed and/or the file is moved from one directory to another (referred to as a “rename” operation), the key associated with its corresponding element in the directory entry hash table will be updated and the element will often move between buckets.
Techniques must be used to perform these hash table operations without impacting readers who may be concurrently performing look-ups on the same file. Moreover, in computing environments conforming to the POSIX (Portable Operating System Interface) standard, the hash table manipulations must be performed atomically. This atomicity requires the following semantics:
If a reader does not see the old item in the hash table, subsequent lookups of the new item must succeed.
If a reader sees the new item, subsequent lookups of the old item must fail.
Two additional requirements must also be imposed in order to ensure correctness:
                The move operation must not cause lookups for other items to fail.        Readers must never block (i.e., there must be bounded latency so that readers are not delayed indefinitely by the move operation).        
Accordingly, a need exists for a technique that allows lockless hash table lookups while performing a key update on a hash table element that results in the element being moved from one hash bucket to another. More generally, because hash table buckets may be thought of individually as linked lists of key-value pairs, there is a related need for an improved strategy for atomically moving shared list elements from one list of key-value pairs to another while maintaining lock-free concurrency between writers and readers.